home *** CD-ROM | disk | FTP | other *** search
/ The Very Best of Atari Inside / The Very Best of Atari Inside 1.iso / mint / mntlib43 / mntlib / qsort.c < prev    next >
C/C++ Source or Header  |  1993-11-02  |  8KB  |  298 lines
  1. /*
  2.  * qsort - parts adapted from Doug Schmidt's sort challenge posting
  3.  *       thanks Doug
  4.  *
  5.  *        ++jrb    bammi@dsrgsun.ces.cwru.edu
  6.  */
  7.  
  8. #if (defined(minix) || defined(unix))
  9. #  include <sys/types.h>
  10. #  if defined(sparc) && !defined(__GNUC__)
  11. #    include <alloca.h>
  12. #  endif
  13. #  ifdef minix    /* minix 1.5 note: size_t as defined in stdlib is not */
  14.         /* used for obvious reasons */
  15. #    include "lib.h"
  16. #  endif
  17. #else
  18. #  include <stddef.h>
  19. #  include <stdlib.h>
  20. #endif
  21. #include <string.h>
  22. #include <memory.h>
  23.  
  24. #ifndef _COMPILER_H
  25. #include <compiler.h>
  26. #endif
  27.  
  28. #ifdef __GNUC__
  29. #  ifdef minix
  30.      void *alloca(unsigned long);
  31.      typedef unsigned long size_t;
  32. #  endif
  33. #  ifdef __GNUC_INLINE__
  34. #    define INLINE    inline
  35. #  else
  36. #    define INLINE    /* */
  37. #  endif
  38. #else
  39. #  define INLINE /* */
  40. #endif
  41.  
  42. /* macros for incrementing/decrementing void pointers */
  43. #define INC(v, size) v = (void *)(((char *)v) + size)
  44. #define DEC(v, size) v = (void *)(((char *)v) - size)
  45.  
  46.     /* the next 4 #defines implement a very fast in-line stack abstraction */
  47.     
  48. #define MAKE_STACK(S) \
  49.     ((stack_node *) alloca((size_t)(sizeof(stack_node) * (S))))
  50. #define PUSH(LOW,HIGH) \
  51.     top->lo = LOW; top->hi = HIGH; top++
  52. #define POP(LOW,HIGH) \
  53.     --top; LOW = top->lo; HIGH = top->hi
  54. #define STACK_NOT_EMPTY \
  55.     (stack < top)                
  56.  
  57. INLINE static void swap __PROTO((unsigned char *, unsigned char *, size_t));
  58. INLINE static void Move __PROTO((unsigned char *, unsigned char *, size_t));
  59. INLINE static void insert_sort __PROTO((void *, void *, size_t, int (*)(const void *, const void *)));
  60. INLINE static void *find_pivot __PROTO((void *, void *, size_t, int (*)(const void *, const void *)));
  61.  
  62. /* Discontinue quicksort algorithm when partition gets below this size. */
  63.  
  64. #ifndef MAX_THRESH
  65. #define MAX_THRESH 15
  66. #endif
  67.  
  68. /* Data structure for stack of unfulfilled obligations. */
  69. typedef struct 
  70. {
  71.     void *lo;
  72.     void *hi;
  73. } stack_node;
  74.  
  75. static void *scratch;    /* scratch mem */
  76.  
  77. /* swap two elements of size n each */
  78. INLINE static void swap(a, b, n)
  79. unsigned char *a, *b;
  80. size_t n;
  81. {
  82.     unsigned char t;
  83.     while(n--)
  84.     {
  85.     t    = *a;
  86.         *a++ = *b;
  87.     *b++ = t;
  88.     }
  89. }
  90.  
  91.  
  92. /* move src to dest */
  93. INLINE static void Move(src, dst, n)
  94. unsigned char *src, *dst;
  95. size_t n;
  96. {
  97.     while(n--)
  98.     *dst++ = *src++;
  99. }
  100.  
  101.  
  102. /* Once main array is partially sorted by quicksort the remainder is 
  103.    completely sorted using insertion sort, since this is efficient 
  104.    for partitions below MAX_THRESH size. BASE points to the beginning 
  105.    of the array to sort, and END_PTR points at the very last element in
  106.    the array (*not* one beyond it!). */
  107.  
  108. INLINE static void 
  109. #if __STDC__
  110.     insert_sort(void *base, void *end_ptr, size_t siz, int (*cmp)(const void *,
  111.                                   const void *))
  112. #else
  113.     insert_sort(base, end_ptr, siz, cmp)
  114.     void *base, *end_ptr;
  115.     size_t siz;
  116.     int (*cmp)();
  117. #endif
  118. {
  119.     void *run_ptr;
  120.     void *tmp_ptr = end_ptr;
  121.     void *temp = scratch;
  122.  
  123.     /* Find the largest element in the array and put it at the 
  124.        end of the array.  This acts like a sentinel, and it speeds
  125.        up the inner loop of insertion sort. */
  126.  
  127.     for (run_ptr = (void *)((char *)end_ptr - siz); run_ptr >= base;
  128.      DEC(run_ptr, siz))
  129.     if ((*cmp)(run_ptr, tmp_ptr) > 0) 
  130.         tmp_ptr = run_ptr;
  131.  
  132.     if(tmp_ptr != end_ptr)
  133.     { swap (tmp_ptr, end_ptr, siz); }
  134.  
  135.     /* Typical insertion sort, but we run from the `right-hand-side'
  136.        downto the `left-hand-side.' */
  137.     
  138.     for (run_ptr = (void *)((char *)end_ptr - siz); run_ptr > base;
  139.      DEC(run_ptr, siz))
  140.     {
  141.     tmp_ptr = (void *)((char *)run_ptr - siz);
  142.     Move(tmp_ptr, temp, siz);
  143.  
  144.     /* Select the correct location for the new element, 
  145.        by sliding everyone down by 1 to make room! */
  146.     
  147. #if 0
  148.     while ((*cmp)(temp , ((char *)tmp_ptr += siz)) > 0)
  149. #else
  150.     while (((INC(tmp_ptr, siz)), (*cmp)(temp, tmp_ptr)) > 0)
  151. #endif
  152.         Move(tmp_ptr, ((unsigned char *)tmp_ptr - siz), siz);
  153.  
  154.     Move(temp, (unsigned char *)tmp_ptr - siz, siz);
  155.     }
  156. }
  157.  
  158. /* Return the median value selected from among the 
  159.    LOW, MIDDLE, and HIGH.  Rearrange LOW and HIGH so
  160.    the three values are sorted amongst themselves. 
  161.    This speeds up later work... */
  162.  
  163. INLINE static void *
  164. #if __STDC__
  165.     find_pivot(void *low, void *high, size_t siz, int (*cmp)(const void *,
  166.                                  const void *))
  167. #else
  168.     find_pivot(low, high, siz, cmp)
  169.     void *low, *high;
  170.     size_t siz;
  171.     int (*cmp)();
  172. #endif
  173. {
  174.     void *middle = (void *) ((char *)low + ((((char *)high - (char *)low)/siz) >> 1) * siz);
  175.     
  176.     if ((*cmp)(middle, low) < 0)
  177.     { swap (middle, low, siz); }
  178.     if ((*cmp)(high, middle) < 0)
  179.     { swap (middle, high, siz); }
  180.     else 
  181.     return middle;
  182.     
  183.     if ((*cmp)(middle, low)  < 0)
  184.     { swap (middle, low, siz); }
  185.     
  186.     return middle;
  187. }
  188.  
  189. /* Order elements using quicksort.  This implementation incorporates
  190.    4 optimizations discussed in Sedgewick:
  191.    
  192.    1. Non-recursive, using an explicit stack of log (n) pointers that 
  193.    indicate the next array partition to sort.
  194.    
  195.    2. Choses the pivot element to be the median-of-three, reducing
  196.    the probability of selecting a bad pivot value.
  197.    
  198.    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
  199.    insertion sort to sort within the partitions.  This is a
  200.    big win, since insertion sort is faster for small, mostly
  201.    sorted array segements.
  202.    
  203.    4. The larger of the 2 sub-partitions are always pushed onto the
  204.    stack first, with the algorithm then concentrating on the
  205.    smaller partition.  This *guarantees* no more than log (n)
  206.    stack size is needed! */
  207.  
  208. void qsort(base, total_elems, size, cmp)
  209. void *base;
  210. size_t total_elems;
  211. size_t size;
  212. int (*cmp) __PROTO((const void *, const void *));
  213. {
  214.     if (total_elems > 1)
  215.     {
  216.     void        *lo;
  217.     void        *hi;
  218.     void        *left_ptr;
  219.     void        *right_ptr;
  220.     void        *pivot;
  221.     size_t        Thresh = MAX_THRESH * size;
  222.     stack_node  *stack;
  223.     stack_node  *top;  
  224.     size_t max_stack_size = 1;
  225.  
  226.     /* Calculate the exact stack space required in the worst case.
  227.        This is approximately equal to the log base 2 of TOTAL_ELEMS. */
  228.     
  229.     {   size_t i;    /* this helps the compiler */
  230.         for (i = 1; i < total_elems; i += i) 
  231.             max_stack_size++;
  232.     }
  233.     /* Create the stack, or die trying! */
  234.     if ((stack = MAKE_STACK (max_stack_size)) != NULL)
  235.         top = stack;
  236.     else
  237.         return;
  238.  
  239.     /* allocate scratch */
  240.     if((scratch = (void *)alloca(size)) == (void *)0)
  241.         return;    /* die */
  242.     
  243.     lo = base;
  244.     hi = (void *) ((char *)lo + (total_elems - 1) * size);
  245.  
  246.     do {
  247.         next: if((char *)hi <= ((char *)lo + Thresh)) /* correct unsigned comapare */
  248.         {
  249.         insert_sort(lo, hi, size, cmp);
  250.         if(STACK_NOT_EMPTY)
  251.             {  POP(lo, hi); goto next; }
  252.         else
  253.             break;
  254.         }
  255.         /* otherwise next iteration of qsort */
  256.         /* Select the median-of-three here. This allows us to
  257.            skip forward for the LEFT_PTR and RIGHT_PTR. */
  258.         pivot = find_pivot (lo, hi, size, cmp);
  259.         left_ptr  = (void *)((char *)lo + size);
  260.         right_ptr = (void *)((char *)hi - size); 
  261.  
  262.         /* Here's the famous ``collapse the walls'' section of
  263.            quicksort.  Gotta like those tight inner loops! */
  264.         do { /* partition loop */  /* see knuth for <= */
  265.         while ((left_ptr < hi) && ((*cmp)(left_ptr, pivot) <= 0))
  266.             INC(left_ptr, size);
  267.         
  268.         while ((right_ptr > lo) && ((*cmp)(pivot, right_ptr) <= 0))
  269.             DEC(right_ptr, size);
  270.         
  271.         if (left_ptr < right_ptr) 
  272.                 {
  273.             swap (left_ptr, right_ptr, size);
  274.             INC(left_ptr,  size);
  275.             DEC(right_ptr, size);
  276.                 }
  277.         else if (left_ptr == right_ptr) 
  278.                 {
  279.             INC(left_ptr, size); 
  280.             DEC(right_ptr, size); 
  281.             break;
  282.                 }
  283.             } while (left_ptr <= right_ptr);
  284.         
  285.         if (((char *)right_ptr - (char *)lo) > ((char *)hi - (char *)left_ptr)) 
  286.             {                   /* push larger left table */
  287.         PUSH (lo, right_ptr);
  288.         lo = left_ptr;
  289.             }
  290.         else 
  291.             {                   /* push larger right table */
  292.         PUSH (left_ptr, hi);
  293.         hi = right_ptr;
  294.             }
  295.         } while(1);    /* when stack is empty it'll break out */
  296.     } /* if total_elems > 1 */
  297. }
  298.